package com.algorithm.sort;

import java.util.Arrays;

/**
 * 构建一个小顶堆
 */
public class HeapSort1 {
    public static void main(String[] args) {
        int[] arr = new int[]{9, 5,11,13,14,53,56,86,90, 2, 1, 4, 6, 3, 7, 8};
        //int[] arr = new int[]{9, 5, 2, 1, 4, 6, 3, 7, 8};
        //buildHeap(arr);
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 构建小顶堆,可以使用上浮和下沉两种
     *
     * @param arr
     */
    public static void buildHeap(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            rise(arr, i);
        }
//        for (int i = arr.length / 2; i >= 0; i--) {
//            sink(arr, i, arr.length);
//        }
    }

    /**
     * 上浮,插入一个数字到堆最后,再执行上浮操作,维持堆大小顺序不变
     *
     * @param arr
     * @param index
     */
    public static void rise(int[] arr, int index) {
        while (true) {
            if (index == 0) break;
            int parentI = (index - 1) / 2;
            if (arr[parentI] > arr[index]) {
                swap(arr, index, parentI);
                index = parentI;
                //rise(arr,parentI);
            } else {
                break;
            }
        }
    }

    /**
     * 下沉,将堆中某个不符合要求的节点向下调整;
     * 由于堆大小不是数组大小,需要判断是否超出范围
     * 如果已经是叶子节点了,就没必要下沉了(无子节点)
     *
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void sink(int[] arr, int index, int heapSize) {
        while (index < heapSize / 2) {
            int li = index * 2 + 1;
            int ri = li + 1;
            if (heapSize == 2){
                System.out.println();
            }
            if (ri > heapSize-1) { //最后一个节点可能只有左叶子没有右叶子
                int l = arr[li];
                int target = arr[index];
                if (l < target) {
                    swap(arr, index, li);
                }
                return;
            } else {
                int mini = arr[li] < arr[ri] ? li : ri;
                if (arr[mini] < arr[index]) {
                    swap(arr, index, mini);
                    index = mini;
                } else {
                    return;
                }
            }
        }
    }

    /**
     * 在构建好小顶堆之后,交换根节点和最后一个叶子节点,将最后一个叶子节点移出堆
     * 此时小顶堆的根节点不满足堆条件,从根开始向下沉
     * 数组大小 = 堆大小 + 已排序结构大小
     * 循环上面操作即可得到逆序排列的数组
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {
        buildHeap(arr);
        for (int i = arr.length-1; i > 0; i--) {
            swap(arr, 0, i);
            sink(arr, 0, i);
        }
    }


    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /**
     * 你到底是在干什么?你以为说出了真相就有任何作用吗?况且你知道的真相不一定就是完全的真相.
     * 思考却不彻底,不一定就比无知更强.当你决定说出什么的时候,请确保自己已经对其完全了解
     * 如果不能完全了解,那么你说出了自己知道的全部真相,也只不过是其中一部分真相.即自己只是说出了部分的真相
     * 谎言是部分的真相,所以你在说谎.为什么你觉得自己在陈述事实,实际上却在说谎?
     * 因为你真正在意的不是对方是否被欺骗,只不过是为了不让自己受这欺骗别人的恶名罢了.为了不让自己背上恶名而去做某件事,
     * 说的是真的还是假的又有多大的区别呢?说到底只不过是为了让自己不难受.这难道不是一种极其自私的行为吗?
     * 既然两种情况都是同样的欺骗和自私,为什么不能选择一种让对方觉得更温暖更愿意接受的呢?
     * 在谈话中我们有义务让对方感到安全和温暖,这难道不是一个男人的基本责任和义务吗?
     * 你究竟是不愿意抛弃什么呢?过去像是飞驰的车轮,不断碾压过我们的思想.我们借以用来思考的东西,恐怕不是真理,恐怕也不是我们已经学到的
     * 自认为的真理,而只不过是仅凭过去的巨大习惯行事而已.对于过去经历的归纳总结形成了我们的思维惯性.
     * 那么如何才能扭转这种思维惯性呢?毕竟为了让我们能一直待在这舒服的简单的思维惯性中,我们早已在潜移默化中将其变成了更加冠冕堂皇
     * 不可撼动的东西-道德.是的,这就是我们的行事逻辑中最最重要、最最让我们无法接受他人观点的原因。道德，一旦我们抢占了这道德的高地，那么我们
     * 就再也不需要担心谁能让我们更改自己的思维方式了。这恐怕是大多数人思想固化的罪魁祸首。当然我不是在说道德不重要，关键是你有多少的切身经历和理解能力
     * 没有实践就没有发言权。我们眼中的以及我们口口声声确信的客观真的是完全客观的吗？恐怕不是。
     *
     *
     */
}
